package com.wj.graph;

import com.wj.linear.Queue;
import com.wj.tree.MinPriorityQueue;
import com.wj.uf.UF_Tree_Weighted;

/**
 * @author wen.jie
 * @date 2021/8/30 14:26
 * Kruskal算法
 */
public class KruskalMST {

    //保存最小生成树的所有边
    private Queue<Edge> mst;

    //索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在 同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
    private UF_Tree_Weighted uf;

    //存储图中所有的边，使用最小优先队列，对边按照权重进行排序
    private MinPriorityQueue<Edge> pq;

    public KruskalMST(EdgeWeightedGraph G) {
        mst = new Queue<>();
        uf = new UF_Tree_Weighted(G.V());
        pq = new MinPriorityQueue<>(G.E());
        for (Edge edge : G.edges()) {
            pq.insert(edge);
        }

        kruskal(G);
    }

    private void kruskal(EdgeWeightedGraph G) {
        while (!pq.isEmpty() && mst.size() < G.V() -1){
            Edge e = pq.delMin();
            int v = e.either();
            int w = e.other(v);
            if (uf.connected(v, w))
                continue;
            uf.union(v, w);
            mst.enqueue(e);
        }
    }

    public Queue<Edge> edges() {
        return mst;
    }

}
